/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/expression-evaluation
@Language: C++
@Datetime: 16-02-09 08:58
*/

class Solution {
    vector<string> convercore(vector<string>&exps,int &i){
        stack<string> strs;
        vector<string> ans;
        for(;i<exps.size();++i){
            if (exps[i]=="+" || exps[i]=="-"){
                strs.push(exps[i]);
            }else if (exps[i]=="*" || exps[i]=="/"){
                if (ans.size()){
                    string s = ans[ans.size()-1];
                    if (s=="+" || s=="-"){
                        ans.pop_back();
                        strs.push(s);
                    }
					else if (s==")")
						ans.pop_back();					
                }
				strs.push(exps[i]);
            }
            else if (exps[i]=="("){
                vector<string> sub = convercore(exps,++i);				
                for(int k=0;k<sub.size();++k)
                    ans.push_back(sub[k]);
				while (strs.size()){
                    ans.push_back(strs.top());
                    strs.pop();
                }
            }
            else if (exps[i]==")"){
                while(strs.size()){
                    ans.push_back(strs.top());
                    strs.pop();
                }
				ans.push_back(")");
                return ans;
            }
            else{
                ans.push_back(exps[i]);
                while (strs.size()){
                    ans.push_back(strs.top());
                    strs.pop();
                }
            }
        }
		while (strs.size()){
            ans.push_back(strs.top());
            strs.pop();
        }
        return ans;
    }
    vector<string> convertToRPN(vector<string> &exps) {
        // write your code here
        int pos=0;
        vector<string> strs= convercore(exps,pos);	
		vector<string> ans;
		for(int i=0;i<strs.size();++i)
			if (strs[i]!=")")
				ans.push_back(strs[i]);
		return ans;
    }
    int evalRPN(vector<string>& tokens) {
        // Write your code here
        stack<int> s;
        int num;
        for(int i=0;i<tokens.size();++i){
            if (tokens[i].length()==1){
            switch(tokens[i][0]){
            case '+':
                num = s.top();
                s.pop();
                num += s.top();
                s.pop();
                s.push(num);
                break;
            case '-':
                num = s.top();
                s.pop();
                num = s.top()-num;
                s.pop();
                s.push(num);
                break;
            case '*':
                num = s.top();
                s.pop();
                num *= s.top();
                s.pop();
                s.push(num);
                break;
            case '/':
                num = s.top();
                s.pop();
                num = s.top()/num;
                s.pop();
                s.push(num);
                break;
            default:
                sscanf(tokens[i].c_str(),"%d",&num);
                s.push(num);
            }
            }
            else{
                sscanf(tokens[i].c_str(),"%d",&num);
                s.push(num);
            }
        }
        num = s.top();
        return num;
    }
public:
    /**
     * @param expression: a vector of strings;
     * @return: an integer
     */
    int evaluateExpression(vector<string> &exps) {
        // write your code here
        if (exps.size()==0) return 0;
        vector<string> rpn = convertToRPN(exps);
        int ans = evalRPN(rpn);
        return ans;
    }
};